/*
 * @lc app=leetcode.cn id=15 lang=swift
 *
 * [15] 三数之和
 */

// @lc code=start
class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        func twoSum(_ nums: [Int], _ start: Int,  _ target: Int) -> [[Int]] {
            var res: [[Int]] = []
            var left = start, right = snums.count-1
            while left < right {
                let sum = snums[left] + snums[right]
                let lNum = snums[left]
                let rNum = snums[right]
                if sum < target {
                    while left < right && snums[left] == lNum { left += 1 }
                } else if sum > target {
                    while left < right && snums[right] == rNum { right -= 1}
                } else {
                    res.append([snums[left], snums[right]])
                    while left < right && snums[left] == lNum { left += 1 }
                    while left < right && snums[right] == rNum { right -= 1}
                }
            }
            return res
        }

        var res: [[Int]] = []
        let snums = nums.sorted()
        // 穷举 threeSum 的第一个数
        var i = 0
        while i < snums.count {
            // 对 target - nums[i] 计算 twoSum
            let twoRes = twoSum(snums, i+1, -snums[i])
            for twoRe in twoRes {
                var re = twoRe
                re.insert(snums[i], at: 0)
                res.append(re)
            }

            // 跳过第一个数字重复的情况，否则会出现重复结果
            while i < snums.count - 1 && snums[i] == snums[i + 1] { i += 1 }

            i += 1
        }

        return res
    }
}
// @lc code=end

